package fina.segmenttree;

import thired.class19_segmenttree.Class01_SegmentTree;

//任务包住格子 懒住 任务没包住格子 分发
public class SegmentTree {
    int[] arr;
    int[] sum;
    int[] lazy;
    int[] change;
    boolean[] update;
    int MAXN;
    public SegmentTree(int[] arr) {
        MAXN = arr.length + 1;
        this.arr = new int[MAXN];
        for(int i = 1;i < MAXN;i++){
            this.arr[i] = arr[i - 1];
        }
        sum = new int[MAXN << 2];
        lazy = new int[MAXN << 2];
        change = new int[MAXN << 2];
        update = new boolean[MAXN << 2];
    }
    public void pushUp(int rt){
        sum[rt] = sum[rt <<1] + sum[rt << 1 | 1];
    }
    public void build(int l,int r,int rt){
        if(l == r){
            sum[rt] = arr[l];
            return;
        }
        int m = (l + r) >> 1;
        build(l,m,rt << 1);
        build(m + 1,r,rt << 1 | 1);
        pushUp(rt);
    }
    public void add(int L,int R,int C,int l,int r,int rt){
        if(L <= l && R >= r){
            sum[rt] += (r - l + 1) * C;
            lazy[rt] += C;
            return;
        }
        int m = (l + r) >> 1;
        //下发
        pushDown(rt,m - l + 1,r - m);
        if(L <= m){
            add(L,R,C,l,m,rt << 1);
        }
        if(R > m){
            add(L,R,C,m + 1,r,rt << 1 | 1);
        }
        pushUp(r);
    }
    public void pushDown(int rt,int ln,int rn){
        if(update[rt]){
            change[rt | 1] = change[rt];
            change[rt << 1 | 1] = change[rt];
            lazy[rt | 1] = 0;
            lazy[rt << 1 | 1] = 0;
            sum[rt|1] = change[rt] * ln;
            sum[rt<<1|1] = change[rt] * rn;
            update[rt] = false;
        }
        if(lazy[rt] != 0){
            sum[rt << 1] += (lazy[rt] * ln);
            sum[rt << 1 | 1] += (lazy[rt] * rn);
            lazy[rt << 1] += lazy[rt];
            lazy[rt << 1 | 1] += lazy[rt];
            lazy[rt] = 0;
        }
    }
    public void update(int L,int R,int C,int l,int r,int rt){
        if(L <= l && R >= r){
            sum[rt] = (r - l + 1) * C;
            lazy[rt] = 0;
            update[rt] = true;
            change[rt] = C;
            return;
        }
        int m = (l + r) >> 1;
        //下发
        pushDown(rt,m - l + 1,r - m);
        if(L <= m){
            update(L,R,C,l,m,rt << 1);
        }
        if(R > m){
            update(L,R,C,m + 1,r,rt << 1 | 1);
        }
        pushUp(r);
    }
    public long query(int L,int R,int l,int r,int rt){
        if(L <= l && R >= r){
            return sum[rt];
        }
        long ans = 0;
        int m = (l + r) >> 1;
        //下发
        pushDown(rt,m - l + 1,r - m);
        if(L <= m){
            ans +=  query(L,R,l,m,rt << 1);
        }
        if(R > m){
            ans += query(L,R,m + 1,r,rt << 1 | 1);
        }
        return ans;
    }

    public static class Right {
        public int[] arr;

        public Right(int[] origin) {
            arr = new int[origin.length + 1];
            for (int i = 0; i < origin.length; i++) {
                arr[i + 1] = origin[i];
            }
        }

        public void update(int L, int R, int C) {
            for (int i = L; i <= R; i++) {
                arr[i] = C;
            }
        }

        public void add(int L, int R, int C) {
            for (int i = L; i <= R; i++) {
                arr[i] += C;
            }
        }

        public long query(int L, int R) {
            long ans = 0;
            for (int i = L; i <= R; i++) {
                ans += arr[i];
            }
            return ans;
        }

    }

    public static int[] genarateRandomArray(int len, int max) {
        int size = (int) (Math.random() * len) + 1;
        int[] origin = new int[size];
        for (int i = 0; i < size; i++) {
            origin[i] = (int) (Math.random() * max) - (int) (Math.random() * max);
        }
        return origin;
    }

    public static boolean test() {
        int len = 100;
        int max = 1000;
        int testTimes = 5000;
        int addOrUpdateTimes = 1000;
        int queryTimes = 500;
        for (int i = 0; i < testTimes; i++) {
            int[] origin = genarateRandomArray(len, max);
            Class01_SegmentTree.SegmentTree seg = new Class01_SegmentTree.SegmentTree(origin);
            int S = 1;
            int N = origin.length;
            int root = 1;
            seg.build(S, N, root);
            Class01_SegmentTree.Right rig = new Class01_SegmentTree.Right(origin);
            for (int j = 0; j < addOrUpdateTimes; j++) {
                int num1 = (int) (Math.random() * N) + 1;
                int num2 = (int) (Math.random() * N) + 1;
                int L = Math.min(num1, num2);
                int R = Math.max(num1, num2);
                int C = (int) (Math.random() * max) - (int) (Math.random() * max);
                if (Math.random() < 0.5) {
                    seg.add(L, R, C, S, N, root);
                    rig.add(L, R, C);
                } else {
                    seg.update(L, R, C, S, N, root);
                    rig.update(L, R, C);
                }
            }
            for (int k = 0; k < queryTimes; k++) {
                int num1 = (int) (Math.random() * N) + 1;
                int num2 = (int) (Math.random() * N) + 1;
                int L = Math.min(num1, num2);
                int R = Math.max(num1, num2);
                long ans1 = seg.query(L, R, S, N, root);
                long ans2 = rig.query(L, R);
                if (ans1 != ans2) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] origin = { 2, 1, 1, 2, 3, 4, 5 };
        SegmentTree seg = new  SegmentTree(origin);
        int S = 1; // 整个区间的开始位置，规定从1开始，不从0开始 -> 固定
        int N = origin.length; // 整个区间的结束位置，规定能到N，不是N-1 -> 固定
        int root = 1; // 整棵树的头节点位置，规定是1，不是0 -> 固定
        int L = 2; // 操作区间的开始位置 -> 可变
        int R = 5; // 操作区间的结束位置 -> 可变
        int C = 4; // 要加的数字或者要更新的数字 -> 可变
        // 区间生成，必须在[S,N]整个范围上build
        seg.build(S, N, root);
        // 区间修改，可以改变L、R和C的值，其他值不可改变
        seg.add(L, R, C, S, N, root);
        // 区间更新，可以改变L、R和C的值，其他值不可改变
        seg.update(L, R, C, S, N, root);
        // 区间查询，可以改变L和R的值，其他值不可改变
        long sum = seg.query(L, R, S, N, root);
        System.out.println(sum);

        System.out.println("对数器测试开始...");
        System.out.println("测试结果 : " + (test() ? "通过" : "未通过"));

    }

}
